Théorème de Bézout

Théorème de Bézout

Soit \(a \in \mathbb{Z}\) et \(b \in \mathbb{Z}\) non nuls.

On a :  \(\mathrm{PGCD}(a;b)=1\) si, et seulement si, il existe \((u;v) \in \mathbb{Z}^2\) tel que \(au+bv=1\) .

Démonstration

On procède par double implication.

\([\Leftarrow]\) On suppose qu'il existe \((u;v) \in \mathbb{Z}^2\) tel que \(au+bv=1\) . On note \(d=\mathrm{PGCD}(a;b)\) .
Alors \(d\) divise \(a\) et \(b\) , donc \(d\) divise toute combinaison linéaire de \(a\) et \(b\) .
En particulier, \(d\) divise \(au+bv=1\) , donc \(d\) divise \(1\) , c'est-à-dire \(d \in \left\lbrace -1;1 \right\rbrace\) .
Or \(d=\mathrm{PGCD}(a;b)>0\) , donc \(d=1\) , et \(a\) et \(b\) sont premiers entre eux.

\([\Rightarrow]\) On suppose que \(\mathrm{PGCD}(a;b)=1\) .

• Dans un premier temps, supposons que \(a>0\) et \(b>0\) .
  On note \(E\) l'ensemble des combinaisons linéaires de \(a\) et \(b\) donnant un résultat strictement positif, c'est-à-dire \(\begin{align*} E=\left\lbrace au+bv \ \vert \ u \in \mathbb{Z} \ ; v \in \mathbb{Z} \ ; au+bv>0 \right\rbrace. \end{align*}\)
  L'ensemble \(E\) est contenu dans \(\mathbb{N}\) , et n'est pas vide (car il contient par exemple \(a=a \times 1+b \times 0\) ).
  Ainsi, cet ensemble possède un plus petit élément, que l'on notera \(d\) .
  Comme \(d \in E\) , il existe deux entiers \(u\) et \(v\) tels que \(d=au+bv\) .
  Considérons la division euclidienne de \(a\) par \(d\) :  \(a=dq+r\)   avec \(0 \leqslant r.
  On a alors \(r=a-dq=a-(au+bv)q =a(1-uq)+b(-vq)\) ,
  donc \(r\) est une combinaison linéaire de \(a\) et \(b\) .
  Or \(0 \leqslant r et \(d\) est le plus petit élément de \(E\) , donc \(r=0\) .
  On a donc \(a=dq\) et donc \(d\) divise \(a\) .
  De manière analogue, en considérant la division euclidienne de \(b\) par \(d\) , on montre que \(d\) divise \(b\) .
  Par conséquent, \(d\) est un diviseur commun à \(a\) et \(b\) .
  Comme \(\mathrm{PGCD}(a;b)=1\) , on a alors \(d \in \left\lbrace -1;1 \right\rbrace\) .
  Or \(d \in E\) , donc \(d>0\) , et ainsi \(d=1\) .
  Finalement, il existe deux entiers \(u\) et \(v\) tels que \(au+bv=1\) .
• Il reste à traiter le cas où \(a<0\) ou \(b<0\) .
  On a : \(\begin{align*} \mathrm{PGCD}(\left\vert a \right\vert;\left\vert b \right\vert)=\mathrm{PGCD}(a;b)=1. \end{align*}\)  
  En appliquant le cas précédent à \(\left\vert a \right\vert\) et \(\left\vert b \right\vert\) ,
  il existe deux entiers \(u\) et \(v\) tels que \(\left\vert a \right\vert u +\left\vert b \right\vert v=1\) .
  Quitte à changer le signe de \(u\) et/ou de \(v\) , cette égalité se réécrit \(au+bv=1\) .